import java.util.HashMap;

/*
 * @lc app=leetcode.cn id=138 lang=java
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Node p = head;
        //复制一遍
        while(p!=null){
            Node temp = p.next;
            p.next = new Node(p.val);
            p.next.next = temp;
            p = temp;
        }
        //生成random
        p = head;
        while(p != null){
            if(p.random != null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        //拆开
        p = head;
        Node cloneHead = p.next;//新链表的头
        Node cloneP = cloneHead;
        while(cloneP.next != null){
            p.next = p.next.next;
            p = p.next;
            cloneP.next = cloneP.next.next;
            cloneP = cloneP.next;
        }
        p.next = null;
        return cloneHead;
    }
}
// @lc code=end

